// 二叉树的前序遍历
var preorderTraversal = function (root) {
  let res = []

  function preorder(root, res) {
    if (root === null) return
    res.push(root.val)
    preorder(root.left, res)
    preorder(root.right, res)
  }

  preorder(root, res)
  return res
}

var preorderTraversal = function (root) {
  let res = []
  if (root === null) return res
  let stack = []
  let node = root
  while (stack.length || node !== null) {
    while (node !== null) {
      res.push(node.val)
      stack.push(node)
      node = node.left
    }
    node = stack.pop()
    node = node.right
  }
  return res
}
